#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/09/27
# @Author   :Changshu
# @File     :practice_169.py

# 169. 多数元素,给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

'''摩尔投票法'
def majorityElement(nums: list) -> int:
	if nums is None or len(nums)==0:
		return None
	count,res=0,nums[0]
	for i in range(0,len(nums)):
		if count==0:
			res=nums[i]
		# 使用Python的三目运算符
		count+=1 if(res==nums[i]) else -1


	return res
'''

'''使用hash'''
def majorityElement(nums: list) -> int:
	if nums is None or len(nums) == 0:
		return None
	d={}
	n=len(nums)
	for i in range(0,n):
		t = nums[i]
		if t in d:
			d[t]+=1
		else:
			d[t]=1
		if d[t] > n // 2:
			return t

if __name__ == '__main__':
	nums=[3,3,4]
	print(majorityElement(nums))